#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

class Solution {
public:
    int memo[31];

    int fib(int n) {
        memset(memo, -1, sizeof memo);
        return dfs(n);
    }

    int dfs(int n)
    {
        if (n <= 1)
        {
            return n;
        }

        if (memo[n] != -1)
        {
            return memo[n];
        }

        memo[n] = dfs(n - 1) + dfs(n - 2);

        return memo[n];
    }
};

int main()
{
	return 0;
}